This invention relates generally to the field of digital computer data communication. The invention relates more specifically to the data link layer and medium access control of a packet message protocol used in a medium such as radio communication or the like where the quantity and capability of stations requiring use of the medium at a given time cannot be predetermined.
As one example of a communication system, consider a system for handling baggage in an airport terminal. Such a system incorporates radio frequency identification (RFID) between interrogators and responders. In such a system, each baggage tag is a responder station. A station in this sense does not imply stationary location but indicates a device that includes a transceiver for communication. As each bag is transported from its origin to its destination, it sequentially enters areas where interrogation and control functions are to be accomplished by one or more interrogators on all baggage tags in the area within a short period of time. In such an application, as well as in applications where inventory, personnel, animals, packages, samples, mobile stations, and objects must be identified and tracked, there remains a need for communication apparatus and protocol having minimal complexity in circuitry, firmware, and software so that stations can be conveniently equipped and used at practical cost. Whether a communication system is practical depends largely on the system designer's choice of a communication protocol.
A protocol is a method employed uniformly by stations using a common communication medium. Using one method, each station can uniformly determine when it may and when it should not attempt transmission on the medium. By following one protocol, efficient communication can be realized; that is to say that each station's objective for communicating can be accomplished with the least delay and the fewest and shortest messages. Communication efficiency could also be defined as the percentage of time during which only one station is transmitting on the medium. Hence, periods when no station is transmitting and periods when more than one station is transmitting are to be avoided. In the latter case, a collision is said to occur and no intelligible message can be received. The central purpose of a protocol is to provide means for arbitrating between stations that would otherwise cause a collision.
Sophisticated protocols achieve high communication efficiency at the expense of circuit and software complexity required at each station using the protocol. The objectives achieved by communication vary with system design and, for example, may include information transfer, remote sensing and control, and shared computational or shared peripheral capability. These objectives are realized by central control of communication or by distributed control. In a system having central access control, permission to use the medium is granted by a central station. When control is distributed, the stations collectively perform a medium access control function to dynamically determine the order in which stations transmit. Of course, interstation communication via the common medium cannot be used to arbitrate. Therefore, the typical protocol includes a set of rules and conditions that each station is constrained in advance to follow. Due to the large number of stations in the modern communication system, random numbers are often employed in arbitration schemes.
Data communication systems have grown in complexity from two-party connections common in the 1970s to systems in the 1990s that interconnect, for example, all employees in a company, all university libraries in a worldwide network, and hundreds of independently managed global networks into a matrix of networks. Such networks are described in "The Matrix, Computer Networks and Conferencing Systems Worldwide" by John S. Quarterman, published by Digital Press, Bedford, Mass. (1990), incorporated in full herein by reference. The rapid increase in the number of stations on these networks has been made possible by the adoption of standard protocols. The majority of these standards use distributed access control so that a network can be formed without agreement to a centralized authority. Network standards and access control are further described in "Handbook of Computer-Communications Standards Volume 2 Local Network Standards," by William Stallings, Ph.D., published by Howard W. Sams & Co., Indianapolis, IN (1988), incorporated in full herein by reference. After widespread adoption of a standard distributed control protocol, changes to the protocol are costly to implement and, therefore, infrequent. Such change ordinarily would require equipment, firmware, or software changes at each station, and coordination to avoid disruption of important communication. Hence, compatibility with existing networks has led communication systems design away from the development of new protocols, especially new protocols having centralized media access control.
There are many commercial digital communication systems using message packets. Radio communication using message packets are also known. Initial amateur radio packet communication employed a simple acknowledge protocol yielding less than 20% communication efficiency. Improved efficiency was later obtained by adopting a standard distributed medium access control protocol. The description by Quarterman and Stallings of radio networks including the ALOHA network, the Packet Radio Network (PRNET), and the Amateur Radio Packet Radio Network (AMPRNET) is included herein by reference.
Existing popular protocols place a heavy burden of software and circuit complexity upon each station. This burden is illustrated in several standard communication protocols that have been developed for networks of physically connected stations. One ring architecture protocol requires each station to monitor its input channel and retransmit on its output channel the incoming message followed by the station's own message, if any. Another protocol requires each station to transmit only within a time slot beginning at a predetermined time after the station receives a header message broadcast on the medium. A third protocol, commercially known as ethernet, requires each station to perform the following steps:
1. Monitor the medium for inactivity.
2. Generate a random number.
3. Wait a time period based in part on the random number.
4. Attempt to transmit.
5. Detect if a portion of its transmission occurred while another station was transmitting and if so.
6. Begin a subsequent attempt to use the medium by monitoring for inactivity.
Such a method adds to the functional complexity of each station.
In systems having no physical connection between stations, i.e. all stations can receive a broadcast simultaneously, there is a need for a protocol independent of a sequential relationship between stations as in a ring architecture. In systems supporting many thousands of potential stations, time slot assignments are impractical.
Suppose an application requires one station to quickly determine whether all stations currently able to use the medium have been interrogated or commanded in order to accomplish a particular objective through communication. In such an application, ethernet would be unsatisfactory because such a determination depends upon the sum of an indeterminate number of time intervals having randomly selected durations.
Thus, there remains a need for a communication system suited for coordinating the use of a common medium among potentially thousands of stations where no physical connection between stations is desirable and interrogation or control activities must be accomplished in limited time. In addition, there remains a need in some applications to minimize the circuit, firmware, and software complexity required at some stations, perhaps at the expense of complexity at other stations. Without decreasing the complexity, the size and cost per station cannot be reduced to permit new and improved communication systems that employ inexpensive disposable stations such as baggage tags, inventory labels, and the like.